\textbf{Aufgabe:}

Bei einer Known-Plaintext.Attacke auf ein Stromchiffre auf LFSR-Basis fallen Ihnen in die Hände:

\begin{tabular}{lr}
Klartext & 1001 0010 0110 1101 1001 0010 0110\\
Chiffretext & 1011 1100 0011 0001 0010 1011 0001\\
\end{tabular}

Ermitteln Sie: Die Größe \textit{n} des internen Registers, dessen Initialisierungzustand $\mathrm{\textit{k}_1\ldots\textit{k}_n}$ und die Rück"-kopplungsfunktion (d.h. die $\mathrm{\textit{c}_j}$).

\textbf{Lösung:}

Aus dem gegebnen Klartext $w$ und dem Chiffretext $E(w)$ erhält man durch $\oplus$ der jeweiligen Stellen von $w$ und $E(w)$ den Schlüsselstrom $z$.

\begin{center}
\begin{tabular}{lr}
$w =$&$1001001001101101100100100110$\\
$E(w) =$&$1011110000110001001010110001$\\
\hline
$z =$&$0010111001011100101110010111$\\
\end{tabular}
\end{center}

Da sich $z$ nach 7 Stellen wiederholt, können wir davon ausgehen, dass $max(n) = 7$ ist. Außerdem können wir ausschließen das $n = 2$ ist, da $0 \oplus 0 \neq 1$ ist. Um die Größe $n$ des internen Registers und die Rückkopplungs"-funktion $c_j$ genau ermitteln zu können, greifen wir auf Linearkombinationen zurück. Aus den ersten 5 Stellen von $z$ lässt sich $c_j$ im Falle $n = 3$ wie folgt abbilden.
\begin{enumerate}
  \item $c_3 * z_1 + c_2 * z_2 + c_1 * z_3 = 0 \Rightarrow c_3 * 0 + c_2 * 0 + c_1 * 1 = 0$
  \item $c_3 * z_2 + c_2 * z_3 + c_1 * z_4 = 1 \Rightarrow c_3 * 0 + c_2 * 1 + c_1 * 0 = 1$
  \item $c_3 * z_3 + c_2 * z_4 + c_1 * z_5 = 1 \Rightarrow c_3 * 1 + c_2 * 0 + c_1 * 1 = 1$
\end{enumerate}
Aus der 1. Formell kann man schließen, dass $c_1 = 0$ ist, da $c_3 * 0$ und $c_2 * 0$ keine Berücksichtigung finden. Die 2. Formell sagt uns, dass $c_2 = 1$ ist, da nun $c_1 * 0$ und $c_3 * 0$ keine Berücksichtigung finden. Da wir wissen das $c_1 = 0$ ist können wir aus der 3. Formell $c_3 = 1$ ermitteln, da hier $c_2 * 0$ keine Berücksichtigung findet. Für den Fall das $n = 3$, wissen wir nun, dass $c_j = 011$ ist.\\
Im Fall $n = 3$ ist der Initialisierungszustand von $k = 001$. Um zu prüfen ob $n$ tatsächlich 3 ist, verrechnen wir $k$ und $c_j$ zu einem Schlüsselstrom. In dem aktuellen Fall ist $n = 3$, da der aus $k$ und $c_j$ berechnete Schlüsselstrom mit $z$ identisch ist.